package com.wfm.leetcode.editor.cn;


import java.util.Arrays;

public class PSeven5颜色分类{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    // 双指针p0和p2，
    // 如果遇到2，交换且P2--，怕交换过后还是0或者2，需要再次判断nums[i],所以得用while而不是if
    // 如果遇到0，交换且P0++
    public void sortColors(int[] nums) {
        int n = nums.length;
        int p0=0,p2=n-1;
        for (int i = 0; i <= p2; i++) {
            // i<=p2是因为i固定，但是随着p2--可能会碰面
            while (nums[i]==2&&i<=p2){
                swap(nums,i,p2);
                p2--;
            }
            if(nums[i]==0){
                swap(nums,i,p0);
                p0++;
            }

        }
    }

    // 双指针，p0 p1,
    // 遇到1交换p1,p1++
    // 遇到0交换p0,判断p1和p0谁在前面，如果p1在前面说明前面有很多1，需要再次交换p[1]和nums[i],p0,p1都++
    // 遇到0两个都++是因为，0不可能被替代了，遇到1只P1++，是因为还可能被后面的0代替。
    // O(n) O(1)
    public void sortColors2(int[] nums) {
        int n = nums.length;
        int p0 = 0, p1 = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) {
                swap(nums,i,p1);
                ++p1;
            } else if (nums[i] == 0) {
                swap(nums,i,p0);
                if (p0 < p1) {
                    swap(nums,i,p1);
                }
                ++p0;
                ++p1;
            }
        }
    }

    // 单指针，两次遍历，第一次遍历遇到0交换，第二次遍历遇到1交换
    // O(n) O(1)
    public void sortColors1(int[] nums) {
        int ptr = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]==0){
                swap(nums,i,ptr);
                ptr++;
            }
        }
        for (int i = ptr; i < nums.length; i++) {
            if(nums[i]==1){
                swap(nums,i,ptr);
                ptr++;
            }
        }
    }
    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PSeven5颜色分类().new Solution();
        int[] ints = {1,2,0};
        solution.sortColors(ints);
        System.out.println(Arrays.toString(ints));
    }
}